package bite;

/**
 * Creared with IntelliJ IDEA.
 * Description:链接：https://www.nowcoder.com/questionTerminal/89844f1f632c475ab6f4a600f71683a8
 * 来源：牛客网
 *
 * We are all familiar with pre-order, in-order and post-order traversals of binary trees. A common problem in data structure classes is to find the pre-order traversal of a binary tree when given the in-order and post-order traversals. Alternatively, you can find the post-order traversal when given the in-order and pre-order. However, in general you cannot determine the in-order traversal of a tree when given its pre-order and post-order traversals. Consider the four binary trees below:
 *
 * All of these trees have the same pre-order and post-order traversals. This phenomenon is not restricted to binary trees, but holds for general m-ary trees as well.
 * User:yxd
 * Date:2022-06-14
 * Time:20:44
 */
import java.util.*;
//一棵树
class SubTree{
    String prev;
    String post;
    public SubTree(String prev,String post){
        this.prev = prev;
        this.post = post;
    }
}
public class Day36_2{
    public static List<SubTree> calcSubTreeNumber(String prev,String post){
        List<SubTree> list = new ArrayList<>();//存放子树
        //从前序树的第一个节点开始,直到结束,前序树的节点就是每一棵子树的根节点,从后续树中找此树有多少个节点
        int prevFirst = 1;//根节点不需要找,是唯一的
        int postFirst = 0;
        while(prevFirst < prev.length()){
            //每个子树的根节点
            char subRoot = prev.charAt(prevFirst);
            //每个子树的个数
            int subCount = post.indexOf(subRoot) - postFirst + 1;
            SubTree subTree = new SubTree(
                    prev.substring(prevFirst,prevFirst + subCount),
                    post.substring(postFirst,postFirst + subCount)
            );
            //将子树放入
            list.add(subTree);
            //然后到下一棵树
            prevFirst += subCount;
            postFirst += subCount;
        }
        return list;
    }

    public static long calcpossible(int n,int m){
        //n叉树,m个子树
        //C(m,n)
        m = m < (n - m) ? m : (n - m);
        long f = 1;
        for(int i = n;i >= (n - m + 1);i --){
            f *= i;
        }
        long w = 1;
        for(int i = 1;i <= m;i ++){
            w *= i;
        }
        return f / w;
    }
    public static long calcSubTreePossible(int m,String prev,String post){
        //通过这个方法计算此树的各种可能性
        if(prev == null || prev.length() == 1){
            //此树为空或者此树只有一个节点
            return 1;
        }
        //再计算出此树有多少个子树
        List<SubTree> list = calcSubTreeNumber(prev,post);
        //然后计算一下这些子树有多少种可能性
        long count = calcpossible(m,list.size());
        for(SubTree s : list){
            //遍历每一个子树,计算出所有子树的可能性
            count *= calcSubTreePossible(m,s.prev,s.post);
        }
        return count;
    }
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        //循环输入处理
        while(input.hasNext()){
            int m = input.nextInt();
            if(m == 0){
                break;
            }
            String prev = input.next();
            String post = input.next();
            System.out.println(calcSubTreePossible(m,prev,post));
        }
    }
}
